﻿
 

namespace Common.Algorithm.Core;

/*
 1 蚂蚁只经过每个点一次
 2 蚂蚁知道城市之间的距离  倾向于最近城市
 3 蚂蚁释放弗洛蒙，距离相同时，走弗洛蒙浓度高的路径
 */

/// <summary>
/// 蚁群算法
/// </summary>
public class AntColonyService
{

    public double alpha { get; set; } = 2;
    public double beta { get; set; } = 5;
    public double Q { get; set; } = 10;
    public double rho { get; set; } = 0.5;

    public int[] path;

    public int cityNum { get; set; }

    public static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

    Matrix<double> matrixDistance;
    Matrix<double> matrixPheromon;
    //Matrix<double> matrixPosibles;

    public List<int> bestPath = new List<int>();

    public AntColonyService(IEnumerable<GraphEdge> edges)
    {
        var groups = edges.GroupBy(e => e.stVertexId);
        this.cityNum = groups.Count();
        matrixDistance = matBuilder.Dense(cityNum, cityNum);
        matrixPheromon = matBuilder.Dense(cityNum, cityNum);

        for (int i = 0; i < cityNum; i++)
        {
            for (int j = 0; j < cityNum; j++)
            {
                matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
                matrixPheromon[i, j] = i == j ? 0 : 0.4;
            }
        }

        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();
    }

    public AntColonyService(Matrix<double> _matrixDistance)
    {
        matrixDistance = _matrixDistance;
        int cityNum = _matrixDistance.RowCount;
          
        matrixDistance = matBuilder.Dense(cityNum, cityNum);
        matrixPheromon = matBuilder.Dense(cityNum, cityNum);

        for (int i = 0; i < cityNum; i++)
        {
            for (int j = 0; j < cityNum; j++)
            { 
                matrixPheromon[i, j] = i == j ? 0 : 0.4;
            }
        }
         
        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();

    }

    public void CreateAntGeneration(int numberOfGeneration)
    {
        for (int i = 0; i < numberOfGeneration; i++)
        {
            //Console.WriteLine($"Number of generation:{i + 1}");
            FindPath();
        }
    }

    public void FindPath()
    {
        var mainPath = path.ToList();
        var tempPath = new List<int>();
        var antNum = mainPath.Count;
        //Dictionary<int, double> probabilities = new Dictionary<int, double>();
        for (int z = 0; z < antNum; z++)
        {
            int stIndex = 0;
            while (mainPath.Count != 0)
            {

                ChooseCity(ref stIndex, mainPath, tempPath);
            }
        }

        UpdatePheromon(tempPath.ToArray());

    }

    public int[] GetBestPath(int stIndex)
    {
        var mainPath = path.ToList();
        var tempPath = new List<int>() { stIndex };
        //Dictionary<int, double> probabilities = new Dictionary<int, double>();
        for (int z = 0; z < 1; z++)
        {
            while (mainPath.Count != 0)
            {
                ChooseCity(ref stIndex, mainPath, tempPath);
            }
        }
        bestPath = tempPath;
        return tempPath.ToArray();
    }

    public void ChooseCity(ref int stIndex, List<int> mainPath, List<int> tempPath)
    {
        Dictionary<int, double> probabilities = new Dictionary<int, double>();
        mainPath.Remove(stIndex);
        if (mainPath.Count == 0) { tempPath.Add(stIndex);return; }
        foreach (var i in mainPath)
        {
            double sum = 0;
            foreach (var j in mainPath)
            {
                var pher = Math.Pow(matrixPheromon[stIndex, j], alpha);
                var dist = Math.Pow((1 / matrixDistance[stIndex, j]), beta);
                sum += dist * pher;
            }

            double curDist = matrixDistance[stIndex, i];
            double curPher = matrixPheromon[stIndex, i];

            double Probability =
                (Math.Pow((1 / curDist), beta) * Math.Pow(curPher, alpha)) / sum;
            Probability = 100 * Probability;
            probabilities.Add(i, Probability);
        }
        probabilities = probabilities.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
        //stIndex = GetNextCity(probabilities);
        if (probabilities.Count != 0) stIndex = probabilities.OrderBy(p => p.Value).Last().Key;//完全按照概率进行
        tempPath.Add(stIndex);
    }

    public int GetNextCity(Dictionary<int, double> dict)
    {
        Random rnd = new Random();
        var moveProb = rnd.Next(1, 100);

        foreach (var pair in dict)
        {
            if (moveProb < pair.Value)
            {
                return pair.Key;
            }
        }
        return 0;
    }

    /// <summary>
    /// 更新信息素浓度
    /// </summary>
    void UpdatePheromon(int[] paths)
    {
        double pathLen = PathLength(paths);
        double avgPheromon = Q / pathLen;//每条走过路径上增加的费洛蒙

        int count = matrixPheromon.RowCount;
        //费洛蒙增量矩阵
        Matrix<double> matrixPheromonDelta = matBuilder.Dense(count, count, 0);
        for (int i = 0; i < paths.Count() - 1; i++)
        {
            int stIndex = paths[i];
            int edIndex = paths[i + 1];
            matrixPheromonDelta[stIndex, edIndex] += avgPheromon;
        }
        //更新信息素浓度
        matrixPheromon = matrixPheromon.Multiply(1d - rho) + matrixPheromonDelta;
    }

    public double PathLength(int[] _paths)
    {
        double pathSum = 0;
        for (int i = 0; i < _paths.Length - 1; i++)
        {
            pathSum += matrixDistance[_paths[i], _paths[i + 1]];
        }
        return pathSum;
    }

}
